package com.mccken.practice.top100.Top_30$.Top_38;

import com.mccken.practice.top100.TreeNode;
import com.mccken.practice.top100.TreeNodeUtil;

/**
 * https://leetcode.cn/problems/diameter-of-binary-tree/?envType=study-plan-v2&envId=top-100-liked
 * <p>
 * 深度遍历
 *
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2024-04-01 23:02
 **/
public class DiameterOfBinaryTree_543 {

	public static void main(String[] args) {
		DiameterOfBinaryTree_543 demo = new DiameterOfBinaryTree_543();
		TreeNode node = TreeNodeUtil.buildTreeNode("1,2,3,4,5");
		TreeNodeUtil.printTreeNode(node);
		System.out.println(demo.diameterOfBinaryTree(node));
	}

	
	int ans = 0;
	public int diameterOfBinaryTree(TreeNode root) {
		if (root == null) {
			return 0;
		}

		depth(root);
		return ans ;

	}
	
	private int depth(TreeNode node) {
		if (node == null) {
			return 0;
		}
		
		int left = depth(node.left);
		int right = depth(node.right);
		ans = Math.max(ans, left+right );
		
		return Math.max(left, right) + 1;
	}
}
